#include <iostream>
#include <vector>
#include <cmath>

/**
 * NowCoder KY8 Integer Split
 */

static const int MOD = 1000000000;

int main() {
    int N;
    scanf("%d", &N);
    std::vector<int> buf(N + 1, 0);
    buf[0] = 1;
    for (int base = 1; base <= N; base <<= 1) 
        for (int i = base; i <= N; i++)
            buf[i] = (buf[i] + buf[i - base]) % MOD;
    printf("%d\n", buf[N]);
}